package set_map.leetcode;

import java.util.HashMap;
import java.util.Map;

class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}

/**
 * @author shkstart
 * @create 2022-11-01-16:22
 */
public class Num138 {
    public Node copyRandomList(Node head) {

//        1.边界条件
        if (head == null) {
            return null;
        }
//        2.建立链表节点的映射关系
        Map<Node, Node> nodeMap = new HashMap<>();
//        3.遍历原链表，新建链表节点，建立映射关系
        for (Node x = head; x != null; x = x.next) {
            Node newNode = new Node(x.val);
            nodeMap.put(x, newNode);
        }
//        4.通过映射关系来连接新链表的next和random
        for (Node x = head; x != null; x = x.next) {
            //旧1.next = 旧2
//            x是旧1，新1是map.get(x)
            //新1.next = 新2
//            新1.next=map.get(x.next)

//            新1
            Node newX = nodeMap.get(x);
//            新1.next=新2
            Node newXNext = nodeMap.get(x.next);
//            新1.random与旧1.random相同映射
            Node newXrandom = nodeMap.get(x.random);
            newX.random = newXrandom;
            newX.next = newXNext;
        }
//     新链表的头节点 nodeMap.get(head)
        return nodeMap.get(head);

    }
}
